package main

import "sync"

// 数组实现队列

type ArrayQueue struct {
	array []string   // 底层切片
	size int		 // 队列的元素数量
	lock sync.Mutex  // 为了并发安全使用的锁
}

// Add 入队操作 尾插法
// 时间复杂度：O(n)
func (queue *ArrayQueue) Add(v string) {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 放入切片中，后进元素放在数组的最后面
	queue.array = append(queue.array, v)

	// 队中元素数量 + 1
	queue.size = queue.size + 1
}

// Remove 出队操作
// 时间复杂度： O(n)
func (queue *ArrayQueue) Remove() string {
	queue.lock.Lock()
	defer queue.lock.Unlock()

	// 队中元素已空
	if (queue.size == 0) {
		panic("empty")
	}

	// 取出队列最前面的元素
	v := queue.array[0]

	/*// 直接原地移动，但是缩容后的空间不会被释放
	for i := 1; i < queue.size; i++ {
		queue.array[i - 1] = queue.array[i]
	}
	// 原数组缩容
	queue.array = queue.array[0: queue.size - 1]*/

	// 创建新的数组，移动次数过多
	newArray := make([]string, queue.size - 1, queue.size - 1)
	for i := 1; i < queue.size; i++ {
		newArray[i - 1] = queue.array[i]
	}
	queue.array = newArray

	// 队中元素数量 - 1
	queue.size = queue.size - 1

	return v
}


func main() {


}
